We derive bounds on the asymptotic density of parity-check matrices and theachievable rates of binary linear block codes transmitted over memorylessbinary-input output-symmetric (MBIOS) channels. The lower bounds on the densityof arbitrary parity-check matrices are expressed in terms of the gap betweenthe rate of these codes for which reliable communication is achievable and thechannel capacity, and the bounds are valid for every sequence of binary linearblock codes. These bounds address the question, previously considered by Sasonand Urbanke, of how sparse can parity-check matrices of binary linear blockcodes be as a function of the gap to capacity. Similarly to a previouslyreported bound by Sason and Urbanke, the new lower bounds on the parity-checkdensity scale like the log of the inverse of the gap to capacity, but theirtightness is improved (except for a binary symmetric/erasure channel, wherethey coincide with the previous bound). The new upper bounds on the achievablerates of binary linear block codes tighten previously reported bounds byBurshtein et al., and therefore enable to obtain tighter upper bounds on thethresholds of sequences of binary linear block codes under ML decoding. Thebounds are applied to low-density parity-check (LDPC) codes, and theimprovement in their tightness is exemplified numerically. The upper bounds onthe achievable rates enable to assess the inherent loss in performance ofvarious iterative decoding algorithms as compared to optimal ML decoding. Thelower bounds on the asymptotic parity-check density are helpful in assessingthe inherent tradeoff between the asymptotic performance of LDPC codes andtheir decoding complexity (per iteration) under message-passing decoding.
展开▼
